Quick Sort - O(NLog(N))..O(N^2) - Divide and Conquer¶
This Divide and Conquer algorithm (comparison sort) is the most often used sorting algorithm.
When configured correctly, it’s extremely efficient and does NOT require the extra space Merge Sort uses.
We partition the list around a Pivot Element, sorting values around the Pivot.
Explanation:
Quick Sort begins by partitioning the list - picking one value of the list
that will be in its sorted place. This value is called a pivot.
All elements smaller than the pivot are moved to its left.
All larger elements are moved to its right.
Knowing that the pivot is in it’s rightful place, we RECURSIVELY sort the values
around the pivot until the entire list is sorted.
Time Complexity:
The worst case scenario is when the smallest or largest element is always selected as the pivot.
This would create partitions of size N-1, causing recursive calls N-1 times.
This leads us to a worst case time complexity of O(N^2).
While this is a terrible worst case, Quick Sort is heavily used because it’s Average Time Complexity
is much quicker. While the partition function utilizes nested while loops,
it does comparisons on all elements of the array to make its swaps.
As such, it has a time complexity of O(n).
With a good Pivot, the Quick Sort function would partition the array into halves which
grows logarithmically with N. Therefore the average time complexity of the Quick Sort algorithm is
O(NLog(N)).
def partition(NL, first_idx, last_idx):
pivot = NL[first]
left_idx = first_idx + 1
right_idx = last_idx
done = False
while not done:
while left_idx <= right_idx and NL[left_idx] <= pivot:
left_idx = left_idx + 1
while NL[right_idx] >= pivot and right_idx >= left_idx:
right_idx = right_idx -1
if right_idx < left_idx:
done = True
else:
NL[left_idx], NL[right_idx] = NL[right_idx], NL[left_idx]
NL[first_idx], NL[right_idx] = NL[right_idx], NL[first_idx]
return right_idx
def quickSortHlp(LON, first_idx, last_idx):
if first_idx < last_idx:
split_index = partition(LON, first_idx, last_idx)
# 2 recursions
quickSortHlp(LON, first_idx, split_index - 1)
quickSortHlp(LON, split_index + 1, last_idx)
def quickSort(LON):
quickSortHlp(LON, 0, len(LON) - 1)
Test:
LON = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quickSort(LON)
print(LON)
Output:
[17, 20, 26, 31, 44, 54, 55, 77, 93]